/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */
package hivemall.utils.math;

import java.util.Arrays;

public final class Primes {

    private static final int[] PRIMES = {3, 5, 7, 13, 19, 31, 43, 61, 73, 89, 103, 109, 139, 151,
            181, 193, 199, 229, 241, 271, 283, 313, 349, 421, 433, 463, 523, 571, 601, 619, 661,
            823, 859, 883, 1021, 1063, 1093, 1153, 1231, 1321, 1429, 1489, 1621, 1699, 1789, 1873,
            1951, 2029, 2131, 2143, 2311, 2383, 2593, 2731, 2803, 3001, 3121, 3259, 3391, 3583,
            3673, 3919, 4093, 4273, 4423, 4651, 4801, 5023, 5281, 5521, 5743, 5881, 6301, 6571,
            6871, 7129, 7489, 7759, 8089, 8539, 8863, 9283, 9721, 10141, 10531, 11071, 11551, 12073,
            12613, 13009, 13759, 14323, 14869, 15649, 16363, 17029, 17839, 18541, 19471, 20233,
            21193, 22159, 23059, 24181, 25171, 26263, 27541, 28753, 30013, 31321, 32719, 34213,
            35731, 37309, 38923, 40639, 42463, 44281, 46309, 48313, 50461, 52711, 55051, 57529,
            60091, 62299, 65521, 68281, 71413, 74611, 77713, 81373, 84979, 88663, 92671, 96739,
            100801, 105529, 109849, 115021, 120079, 125509, 131011, 136861, 142873, 149251, 155863,
            162751, 169891, 177433, 185071, 193381, 202129, 211063, 220021, 229981, 240349, 250969,
            262111, 273643, 285841, 298411, 311713, 325543, 339841, 355009, 370663, 386989, 404269,
            422113, 440809, 460081, 480463, 501829, 524221, 547399, 571603, 596929, 623353, 651019,
            679909, 709741, 741343, 774133, 808441, 844201, 881539, 920743, 961531, 1004119,
            1048573, 1094923, 1143283, 1193911, 1246963, 1302181, 1359733, 1420039, 1482853,
            1548541, 1616899, 1688413, 1763431, 1841293, 1922773, 2008081, 2097133, 2189989,
            2286883, 2388163, 2493853, 2604013, 2719669, 2840041, 2965603, 3097123, 3234241,
            3377191, 3526933, 3682363, 3845983, 4016041, 4193803, 4379719, 4573873, 4776223,
            4987891, 5208523, 5439223, 5680153, 5931313, 6194191, 6468463, 6754879, 7053331,
            7366069, 7692343, 8032639, 8388451, 8759953, 9147661, 9552733, 9975193, 10417291,
            10878619, 11360203, 11863153, 12387841, 12936529, 13509343, 14107801, 14732413,
            15384673, 16065559, 16777141, 17519893, 18295633, 19105483, 19951231, 20834689,
            21757291, 22720591, 23726449, 24776953, 25873963, 27018853, 28215619, 29464579,
            30769093, 32131711, 33554011, 35039911, 36591211, 38211163, 39903121, 41669479,
            43514521, 45441199, 47452879, 49553941, 51747991, 54039079, 56431513, 58930021,
            61539091, 64263571, 67108669, 70079959, 73182409, 76422793, 79806229, 83339383,
            87029053, 90881083, 94906249, 99108043, 103495879, 108077731, 112863013, 117860053,
            123078019, 128526943, 134217439, 140159911, 146365159, 152845393, 159612601, 166679173,
            174058849, 181765093, 189812341, 198216103, 206991601, 216156043, 225726379, 235720159,
            246156271, 257054491, 268435009, 280319203, 292730833, 305691181, 319225021, 333358513,
            348117151, 363529759, 379624279, 396432481, 413983771, 432312511, 451452613, 471440161,
            492312523, 514109251, 536870839, 560640001, 585461743, 611382451, 638450569, 666717199,
            696235363, 727060069, 759249643, 792864871, 827967631, 864625033, 902905501, 942880663,
            984625531, 1028218189, 1073741719, 1121280091, 1170923713, 1222764841, 1276901371,
            1333434301, 1392470281, 1454120779, 1518500173, 1585729993, 1655935399, 1729249999,
            1805811253, 1885761133, 1969251079, 2056437379, 2147482951, Integer.MAX_VALUE};

    private Primes() {}

    /**
     * Returns from a static prime table the least prime that is greater than or equal to a
     * specified value.
     */
    public static int findLeastPrimeNumber(final int n) {
        assert (n >= 0) : n;
        int idx = Arrays.binarySearch(PRIMES, n);
        if (idx < 0) {
            idx = -idx - 1;
            if (idx >= PRIMES.length) {
                idx = PRIMES.length - 1;
            }
            return PRIMES[idx]; // if not found, use max prime (in this case 9973).
        }
        return PRIMES[idx];
    }
}
